<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    1022. Unique Paths III
   </h1>
   <p>
    On a 2-dimensional&nbsp;
    <code>
     grid
    </code>
    , there are 4 types of squares:
   </p>
   <ul>
    <li>
     <code>
      1
     </code>
     represents the starting square.&nbsp; There is exactly one starting square.
    </li>
    <li>
     <code>
      2
     </code>
     represents the ending square.&nbsp; There is exactly one ending square.
    </li>
    <li>
     <code>
      0
     </code>
     represents empty squares we can walk over.
    </li>
    <li>
     <code>
      -1
     </code>
     represents obstacles that we cannot walk over.
    </li>
   </ul>
   <p>
    Return the number of 4-directional walks&nbsp;from the starting square to the ending square, that
    <strong>
     walk over every non-obstacle square&nbsp;exactly once
    </strong>
    .
   </p>
   <p>
    &nbsp;
   </p>
   <div>
    <p>
     <strong>
      Example 1:
     </strong>
    </p>
    <pre>
<strong>Input: </strong><span id="example-input-1-1">[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]</span>
<strong>Output: </strong><span id="example-output-1">2</span>
<strong>Explanation: </strong>We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)</pre>
    <div>
     <p>
      <strong>
       Example 2:
      </strong>
     </p>
     <pre>
<strong>Input: </strong><span id="example-input-2-1">[[1,0,0,0],[0,0,0,0],[0,0,0,2]]</span>
<strong>Output: </strong><span id="example-output-2">4</span>
<strong>Explanation: </strong>We have the following four paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)</pre>
     <div>
      <p>
       <strong>
        Example 3:
       </strong>
      </p>
      <pre>
<strong>Input: </strong><span id="example-input-3-1">[[0,1],[2,0]]</span>
<strong>Output: </strong><span id="example-output-3">0</span>
<strong>Explanation: </strong>
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.
</pre>
     </div>
    </div>
   </div>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ol>
    <li>
     <code>
      1 &lt;= grid.length * grid[0].length &lt;= 20
     </code>
    </li>
   </ol>
  </div>
  <div>
   <h1 class="question_title">
    1022. 不同路径 III
   </h1>
   <p>
    在二维网格
    <code>
     grid
    </code>
    上，有 4 种类型的方格：
   </p>
   <ul>
    <li>
     <code>
      1
     </code>
     表示起始方格。且只有一个起始方格。
    </li>
    <li>
     <code>
      2
     </code>
     表示结束方格，且只有一个结束方格。
    </li>
    <li>
     <code>
      0
     </code>
     表示我们可以走过的空方格。
    </li>
    <li>
     <code>
      -1
     </code>
     表示我们无法跨越的障碍。
    </li>
   </ul>
   <p>
    返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目，
    <strong>
     每一个无障碍方格都要通过一次
    </strong>
    。
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例 1：
    </strong>
   </p>
   <pre><strong>输入：</strong>[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
<strong>输出：</strong>2
<strong>解释：</strong>我们有以下两条路径：
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)</pre>
   <p>
    <strong>
     示例 2：
    </strong>
   </p>
   <pre><strong>输入：</strong>[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
<strong>输出：</strong>4
<strong>解释：</strong>我们有以下四条路径： 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)</pre>
   <p>
    <strong>
     示例 3：
    </strong>
   </p>
   <pre><strong>输入：</strong>[[0,1],[2,0]]
<strong>输出：</strong>0
<strong>解释：</strong>
没有一条路能完全穿过每一个空的方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     <code>
      1 &lt;= grid.length * grid[0].length &lt;= 20
     </code>
    </li>
   </ol>
  </div>
 </body>
</html>